package main

import "fmt"

var (
	_ = fmt.Printf

	board                 [][]int
	rowCount, columnCount int

	rowHints, columnHints           [][]int
	rowCandidates, columnCandidates [][][]int
)

const (
	stateUnknown = iota // 0
	stateTrue    = iota // 1
	stateFalse   = iota // 2
)

func shift(blocks []int, displacement int) {
	for i, _ := range blocks {
		blocks[i] = blocks[i] + displacement
	}
}

func leftmostSpace(line []int, after, blockSize int) int {
	lineSize := len(line)
	for i := after; i <= (lineSize - blockSize); i++ {
		for j := 0; j < blockSize; j++ {
			if line[i+j] == stateFalse {
				break
			}

			if j == (blockSize - 1) {
				return i
			}
		}
	}
	return -1
}

func rightmostSpace(line []int, hereOrBefore, blockSize int) int {
	for i := hereOrBefore - (blockSize - 1); i >= 0; i-- {
		for j := 0; j < blockSize; j++ {
			if line[i+j] == stateFalse {
				// i is invalid position. We should try one cell left.
				break
			}
			if j == (blockSize - 1) {
				return i
			}
		}
	}
	return -1
}

func rightmostSpaceBeforeBlocks(line, blocksAfter []int, blockSize int) int {
	rangeEnd := len(line) - 1
	for i := len(blocksAfter) - 1; i >= 0; i-- {
		rangeEnd = rightmostSpace(line, rangeEnd, blocksAfter[i]) - 2
	}
	return rightmostSpace(line, rangeEnd, blockSize)
}

func leftmostPositionsWithFalseRestriction(line, hint []int) []int {
	blockCount := len(hint)
	result := make([]int, blockCount)
	newBlockStart := 0
	for i := 0; i < blockCount; i++ {
		blockSize := hint[i]
		position := leftmostSpace(line, newBlockStart, blockSize)
		if position == -1 {
			return nil
		}
		result[i] = position
		// position + block size + least size border
		newBlockStart = position + blockSize + 1
	}
	return result
}

func positionsToSequence(size int, hint, positions []int) []int {
	ret := make([]int, size)
	for i := 0; i < size; i++ {
		ret[i] = stateFalse
	}
	for i, p := range positions {
		for j := p; j < p+hint[i]; j++ {
			ret[j] = stateTrue
		}
	}
	return ret
}

func isValidWithTrueRestriction(line, hint, positions []int) bool {
	isValid := true
	for i, c := range line { // index i, state value c
		if c == stateTrue {
			isCellValid := false
			for j, s := range positions {
				if s <= i && i < s+hint[j] {
					isCellValid = true
					break
				}
			}
			if !isCellValid {
				return false
			}
		}
	}
	return isValid
}

func nextPositions(line, current, hint []int) []int {
	blockCount := len(hint)

	for i := blockCount - 1; i >= 0; i-- {
		// i is the index of the block, who is being checked if can move to right
		position := current[i]
		size := hint[i]
		// Blocks which are right to current block
		afters := hint[i+1:]
		last := rightmostSpaceBeforeBlocks(line, afters, size)

		if (last == -1) || (position == last) {
			// Current block is already rightmost.
			// Check if the block left to current can move right
			// and current block goes to left most accordingly if possible.
			continue
		}

		position++
		newRight := leftmostPositionsWithFalseRestriction(line[position:], hint[i:])
		shift(newRight, position)
		return append(current[:i], newRight...)

	}
	return nil
}

func getPossiblePositions(line, hint []int) [][]int {
	ret := make([][]int, 0)

	positions := leftmostPositionsWithFalseRestriction(line, hint)
	for positions != nil {
		if isValidWithTrueRestriction(line, hint, positions) {
			copyedSequence := make([]int, len(positions))
			copy(copyedSequence, positions)
			ret = append(ret, copyedSequence)
		}
		positions = nextPositions(line, positions, hint)
	}
	return ret
}

func findStates(line, hint []int, positions [][]int) {
	sequences := make([][]int, 0)
	for _, p := range positions {
		s := positionsToSequence(len(line), hint, p)
		sequences = append(sequences, s)
	}

	for i, cell := range line {
		if cell == stateUnknown {
			prevCaseValue := stateUnknown
			for _, s := range sequences {
				curCaseValue := s[i]
				if prevCaseValue != stateUnknown && prevCaseValue != curCaseValue {
					prevCaseValue = stateUnknown
					break
				}
				prevCaseValue = curCaseValue
			}
			line[i] = prevCaseValue
		}
	}
}

func initBoard() {
	board = make([][]int, rowCount)
	for rIndex := 0; rIndex < rowCount; rIndex++ {
		row := make([]int, columnCount)
		for colIndex := 0; colIndex < columnCount; colIndex++ {
			row[colIndex] = stateUnknown
		}
		board[rIndex] = row
	}
}

func printLine(line []int) {
	for _, cell := range line {
		switch cell {
		case stateUnknown:
			fmt.Print("▣")
		case stateTrue:
			fmt.Print("■")
		case stateFalse:
			fmt.Print("□")
		}
	}
	fmt.Printf("\n")
}

func readRow(i int) []int {
	ret := make([]int, columnCount)
	copy(ret, board[i])
	return ret
}

func writeRow(i int, row []int) {
	copy(board[i], row)
}

func readColumn(cIndex int) []int {
	ret := make([]int, rowCount)
	for i, row := range board {
		ret[i] = row[cIndex]
	}
	return ret
}

func writeColumn(cIndex int, column []int) {
	for i, row := range board {
		row[cIndex] = column[i]
	}
}

func main() {
	rowCount = 30
	columnCount = 30

	initBoard()

	// init hints
	rowHints = [][]int{{4}, {6}, {5, 1}, {5, 1}, {4, 1},
		{2, 1}, {2, 1}, {2, 1}, {2, 4}, {2, 5},
		{2, 7}, {2, 9}, {2, 9, 2}, {4, 10, 4}, {15, 6},
		{22}, {2, 17}, {4, 16}, {5, 11, 2}, {6, 9, 4},
		{6, 6, 3, 2}, {7, 4, 3, 3}, {7, 3, 3, 2, 3}, {7, 4, 3, 2, 3}, {1, 5, 3, 3, 3, 3},
		{3, 8, 1, 2, 2}, {3, 7, 3, 3}, {7, 3, 3}, {3, 3, 2}, {4}}
	columnHints = [][]int{{0}, {12}, {10, 1}, {3, 7, 2}, {3, 8, 1},
		{12, 7, 2}, {14, 7, 1}, {2, 4, 5, 2}, {3, 7, 5}, {2, 10, 4},
		{3, 15}, {2, 16}, {3, 10, 4}, {2, 10, 2, 2}, {2, 10, 1, 2},
		{20, 2, 1}, {6, 5, 1, 2, 2}, {11, 2, 1, 2}, {5, 5, 1, 2, 1, 2}, {9, 2, 1, 1, 1},
		{2, 5, 1, 2, 2, 2}, {10, 1, 2, 2}, {9, 1, 1}, {2, 2, 2}, {1, 1, 1},
		{2, 2}, {4}, {3}, {2}, {0}}

	rowCandidates = make([][][]int, rowCount)
	columnCandidates = make([][][]int, columnCount)

	notFixed := true
	for notFixed {
		for rIndex := 0; rIndex < rowCount; rIndex++ {
			line := readRow(rIndex)
			candidates := getPossiblePositions(line, rowHints[rIndex])
			findStates(line, rowHints[rIndex], candidates)

			writeRow(rIndex, line)
			rowCandidates[rIndex] = candidates
		}

		for cIndex := 0; cIndex < columnCount; cIndex++ {
			line := readColumn(cIndex)
			candidates := getPossiblePositions(line, columnHints[cIndex])
			findStates(line, columnHints[cIndex], candidates)

			writeColumn(cIndex, line)
			columnCandidates[cIndex] = candidates
		}

		notFixed = false
		for _, rCandidate := range rowCandidates {
			if len(rCandidate) > 1 {
				notFixed = true
			}
		}
	}

	for rIndex := 0; rIndex < rowCount; rIndex++ {
		line := readRow(rIndex)
		printLine(line)
	}
}
